package com.practice.niuke.new_direct_basics.class04;

/**
 * 反转一个单链表、反转一个双链表
 */
public class Code02_ReverseList {

	/**
	 * 单链表节点类型
	 */
	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	/**
	 * 反转一个单链表
	 *
	 * @param head 单链表表头
	 * @return 反转后的头节点
	 */
	public static Node reverseList(Node head) {
		// 1. 设head为当前节点
		// 1.1 pre指针用于记录当前节点的前一个节点，初始时为null
		Node pre = null;
		// 1.2 next指针用于记录当前节点的下一个节点，初始时为null
		Node next = null;
		// 2. 遍历链表，只要当前节点（head）不为null，一直遍历下去
		while (head != null) {
			// 2.1 抓取（记录）一下当前节点（head）的下一个节点
			next = head.next;
			// 2.2 将当前节点（head）的next指针指向当前节点的前一个节点pre
			head.next = pre;
			// 2.3 将当前节点的前一个节点指向当前节点自己
			pre = head;
			// 2.4 当前节点指向，2.1步拿到的原先的下一个节点位置
			head = next;
		}
		// 3. 此时当前节点为null，当前节点的前一个节点pre就是需要的新头部
		return pre;
	}

	/**
	 * 双向链表节点类型
	 */
	public static class DoubleNode {
		public int value;
		public DoubleNode last;
		public DoubleNode next;

		public DoubleNode(int data) {
			this.value = data;
		}
	}

	/**
	 * 反转一个双链表
	 *
	 * @param head 双链表表头
	 * @return 反转后的头节点
	 */
	public static DoubleNode reverseList(DoubleNode head) {
		// 用于记一个前面的环境
		DoubleNode pre = null;
		// 用于记一个后面的环境
		DoubleNode next = null;
		// 遍历链表，只要当前节点（head）不为null，一直遍历下去
		while (head != null) {
			// 先记好当前节点的next环境
			next = head.next;
			// 当前节点的前一个指针指向前一个节点
			head.next = pre;
			// 当前节点的last指针指向后一个节点（之前记录的next环境）
			head.last = next;
			// 当前节点的前一个节点指向当前节点
			pre = head;
			// 将当前节点指向之前记录的next环境
			head = next;
		}
		return pre;
	}

	/**
	 * 打印单向链表
	 *
	 * @param head 单向链表的头节点
	 */
	public static void printLinkedList(Node head) {
		System.out.print("Linked List: ");
		while (head != null) {
			System.out.print(head.value + " ");
			head = head.next;
		}
		System.out.println();
	}

	/**
	 * 打印双向链表
	 *
	 * @param head 双向链表的头节点
	 */
	public static void printDoubleLinkedList(DoubleNode head) {
		System.out.print("Double Linked List: ");
		DoubleNode end = null;
		while (head != null) {
			System.out.print(head.value + " ");
			end = head;
			head = head.next;
		}
		System.out.print("| ");
		while (end != null) {
			System.out.print(end.value + " ");
			end = end.last;
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Node head1 = new Node(1);
		head1.next = new Node(2);
		head1.next.next = new Node(3);
		printLinkedList(head1);
		head1 = reverseList(head1);
		printLinkedList(head1);

		DoubleNode head2 = new DoubleNode(1);
		head2.next = new DoubleNode(2);
		head2.next.last = head2;
		head2.next.next = new DoubleNode(3);
		head2.next.next.last = head2.next;
		head2.next.next.next = new DoubleNode(4);
		head2.next.next.next.last = head2.next.next;
		printDoubleLinkedList(head2);
		printDoubleLinkedList(reverseList(head2));

	}

}
